/**
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 *
 * 实现词典类 WordDictionary ：
 *
 * WordDictionary() 初始化词典对象
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * bool search(word) 如果数据结构中存在字符串与word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个. 都可以表示任何一个字母。
 *
 * 链接：https://leetcode.cn/problems/design-add-and-search-words-data-structure
 * 
 */
class WordDictionary {
    private static class TrieNode {
        TrieNode[] children=new TrieNode[26];
        boolean isVal=false;
    }
    private TrieNode root;
    public WordDictionary() {
        root=new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode p=root;
        int len=word.length();
        for(int i=0;i<len;i++) {
            char c=word.charAt(i);
            if(p.children[c-'a']==null) {
                p.children[c-'a']=new TrieNode();
            }
            p=p.children[c-'a'];
        }
        p.isVal=true;
    }
    
    public boolean search(String word) {
        return search(root,word,0);
    }
    public boolean search(TrieNode node,String word,int i) {
        if(node==null) {
            return false;
        }
        if(i==word.length()) {
            return node.isVal;
        }
        char c=word.charAt(i);
        if(c!='.') {
            if(search(node.children[c-'a'],word,i+1)) {
                return true;
            }
        } else {
            for(int j=0;j<26;j++) {
                if(search(node.children[j],word,i+1)) {
                    return true;
                }
            }
            
        }
        return false;
    }
}
